// 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

// 必须 原地 修改，只允许使用额外常数空间。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/next-permutation
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 冒泡排序 n^2
// 执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 35.47%
// 的用户
// 内存消耗：
// 11.9 MB
// , 在所有 C++ 提交中击败了
// 6.06%
// 的用户


#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<set>
using namespace std;
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len=nums.size();
        if(len<3){
            sort(nums.begin(),nums.end());
        }
        int pos = len-1;
        while(pos>0){
            if(nums[pos]>nums[pos-1]){
                int min_num = nums[pos];
                int min_num_pos = pos;
                for(int j=pos;j<len;j++){
                    if(nums[j]>nums[pos-1] && nums[j]<min_num){
                        min_num=nums[j];
                        min_num_pos = j;
                    }
                }
                int temp = nums[pos-1];
                nums[pos-1] = min_num;
                nums[min_num_pos] = temp;
                // 冒泡排序
                // for(int i = pos;i<len;i++){
                //     int temp =nums[i];
                //     int temp_pos = i;
                //     for(int j=i+1;j<len;j++){
                //         if(nums[i]>nums[j]){
                //             nums[i] = nums[j];
                //             temp_pos = j;
                //         }
                //     }
                //     nums[temp_pos] = temp;
                // }
                return;
            }
            else{
                pos--;
            }
        }
        sort(nums.begin(),nums.end());
        return;
    }
};